from collections import defaultdict
from typing import List


def findSubstring(s: str, words: List[str]) -> List[int]:
    if not s or not words:
        return []

    word_length = len(words[0])  # 每个单词的长度
    word_count = len(words)  # 单词的总数
    total_length = word_length * word_count  # 串联子串的总长度
    s_length = len(s)  # 目标字符串的长度
    result = []  # 存储结果的起始索引

    # 构建单词频率字典
    word_frequency = defaultdict(int)
    for word in words:
        word_frequency[word] += 1

    # 从不同的起始偏移量开始检查（0到word_length-1）
    for i in range(word_length):
        left = i  # 滑动窗口左边界
        right = i  # 滑动窗口右边界
        current_frequency = defaultdict(int)  # 当前窗口内的单词频率
        matched = 0  # 匹配的单词数量

        # 确保右边界加上单词长度不超过字符串长度
        while right + word_length <= s_length:
            # 提取当前单词
            current_word = s[right:right + word_length]
            right += word_length  # 右边界右移

            # 如果当前单词在目标单词列表中
            if current_word in word_frequency:
                current_frequency[current_word] += 1
                matched += 1

                # 如果当前单词出现次数超过预期，需要移动左边界调整窗口
                while current_frequency[current_word] > word_frequency[current_word]:
                    left_word = s[left:left + word_length]
                    current_frequency[left_word] -= 1
                    matched -= 1
                    left += word_length  # 左边界右移

                # 当匹配的单词数量等于目标数量时，记录起始索引
                if matched == word_count:
                    result.append(left)
            else:
                # 如果单词不在目标列表中，重置窗口
                current_frequency.clear()
                matched = 0
                left = right  # 左边界直接跳到右边界

    return result


# 测试用例
if __name__ == "__main__":
    test_cases = [
        ("barfoothefoobarman", ["foo", "bar"], [0, 9]),
        ("wordgoodgoodgoodbestword", ["word", "good", "best", "word"], []),
        ("barfoofoobarthefoobarman", ["bar", "foo", "the"], [6, 9, 12]),
        ("lingmindraboofooowingdingbarrwingmonkeypoundcake", ["fooo", "barr", "wing", "ding", "wing"], [13])
    ]

    for s, words, expected in test_cases:
        s, words, expected = ("abcdcdabcd", ["ab", "cd"], [13])
        result = findSubstring(s, words)
        # 排序后比较，因为结果可以是任意顺序
        assert sorted(result) == sorted(expected), f"测试失败: {result} 不等于 {expected}"
    print("所有测试用例通过!")
